package leecode;

public class LeetCode30 {
    public int[] printNumbers(int n) {
        int[]arr=new int[(int)Math.pow(10,n)-1];
        for (int i = 1; i <Math.pow(10,n) ; i++) {
            arr[i-1]=i;
        }
        return arr;
    }
    /**
     * 求逆序对（归并排序）
     */
    public int reversePairs(int[] nums) {
        if(nums.length<2){
            return 0;
        }
        int left=0;
        int right=nums.length-1;
        int[]arr=new int[nums.length];//辅助数组后面要用，现在创建避免后面递归不停创建
        int a= reversePairs(nums,left,right,arr);
        return a;
    }

    private int reversePairs(int[] nums, int left, int right,int[]arr) {
        if(left==right){
            return 0;
        }
        int mid=left+(right-left)/2;
        int leftnumb=reversePairs(nums,left,mid,arr);
        int rightnumb=reversePairs(nums,mid+1,right,arr);
        int count=count(nums,left,mid,right,arr);
        return count+rightnumb+leftnumb;
    }

    private int count(int[] nums, int left, int mid, int right, int[] arr) {
        for (int i = left; i <=right ; i++) {
            arr[i]=nums[i];
        }
        int l=left;
        int r=mid+1;
        int count=0;
        for (int i = left; i <= right; i++) {
            if(l==mid+1){
                    nums[i]=arr[r];
                    r++;
            }else if(r==right+1){
                    nums[i]=arr[l];
                    l++;
            }else if(arr[l]<=arr[r]){
                nums[i]=arr[l];
                l++;
            }else {
                nums[i]=arr[r];
                r++;
                count+=mid-l+1;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        LeetCode30 leetCode30=new LeetCode30();
        int[] arr={7,5,6,4};
        leetCode30.reversePairs(arr);
    }
}
